GATE PYQ

GATE CSE 1992

Q1.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: A 2-3 tree is such that a. All internal nodes have either 2 or 3 children b. All paths from root to the leaves have the same length.The number of internal nodes of a 2-3 tree having 9 leaves could be

Q2.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Context-free languages are:

Q3.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: If G is a context free grammar and w is a string of length l in L(G), how long is a derivation of w in G, if G is in Chomsky normal form?

Q4.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: For a context free grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of non-terminal A in some "sentential" form. We define two sets LFOLLOW(A) and RFOLLOW(A) by replacing the word "sentential" by "left sentential" and "right most sentential" respectively in the definition of FOLLOW (A).

Q5.
Choose the correct alternatives (more than one may be correct ) and write the corresponding letters only: Consider the SLR(1) and LALR (1) parsing tables for a context free grammar. Which of the following statement is/are true?

Q6.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: A computer system has 6 tape devices, with n processes competing for them. Each process may need 3 tape drives. The maximum value of n for which the system is guaranteed to be deadlock-free is:

Q7.
Mention the pass number for each of the following activities that occur in a two pass assembler: A. object code generation B. literals added to literal table C. listing printed D. address resolution of local symbols

Q8.
Choose the correct alternatives ( more than one may be correct) and write the corresponding letters only:A non-planar graph with minimum number of vertices has

Q9.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Which of the following regular expression identities is/are TRUE?

Q10.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Following algorithm(s) can be used to sort n in the range [1\ldots n^3] in O(n) time